#include <vector>
#include <queue>
#include <stack>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <iterator>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <cstdlib>
#include <windows.h>

using namespace std;

const int Max_Len = 50;//DFS最大深度

struct status
{
	vector<int>v;
	int depth;
};
struct cmp//定义代价计算的方式，开销计算以与目标状态的差距为基准
{
	bool operator () (status a, status b) // 重载括号
	{
		return a.depth > b.depth;//代价小的优先级高
	}
};

class AI_Puzzle
{
public:
	AI_Puzzle() { ; };
	AI_Puzzle(const vector<int>& init_state) {
		m_init_state.assign(init_state.begin(), init_state.end());
	};
	~AI_Puzzle() { ; };
	DWORD begin,end;//记录时间
public:
	// set the init state
	void setInitState(const vector<int>& init_state) {
		m_init_state.assign(init_state.begin(), init_state.end());//copy
	};

	//
	// please fill three types of solver to find the solution
	// 
	// return true if the problem has solution
	// return false if the problem does not have solution
	// results: the output sequences of states
	// 
	// We want the final state is
	//
	//		1	2	3
	//		4	5	6
	//		7	8	0
	//
	bool solution(vector<vector<int>>& results)
	{
		int option;
		bool state=false;
		printf("choose which solution you will take\n");
		printf("1.BFS;\n2.DFS;\n3.UCS;\n");
		scanf("%d",&option);
		switch(option)
		{
			case 1:
			state=BFS(results);
			case 2:
			state=DFS(results);
			case 3:
			state=UCS(results);
			default:
			break;
		}
		cout<<"Time:"<<(end-begin)<<"ms"<<endl;
		return state;
	}

private:
	// bfs to find the solution
	//bfs reference: https://yanjiang.blog.csdn.net/article/details/86768836?spm=1001.2101.3001.6650.2&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-2.no_search_link&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-2.no_search_link
	bool BFS(vector<vector<int>>& results)
	{
		begin = ::GetTickCount();//返回自设备启动后的毫秒数
		//int move[4][2]={{-1 0},{1 0},{0 -1},{0 1}};
		queue<vector<int>> bfs_q;//队列实现
		map<vector<int>, string> hash;//hash判断是否存在重复的情况
		map<vector<int>, vector<int>> father; //记录每种情况的父节点
		int dx[] = { -1,1,0,0 };
		int dy[] = { 0,0,-1,1 };
		bfs_q.push(m_init_state);
		while (!bfs_q.empty())
		{
			vector<int> first = bfs_q.front();
			bfs_q.pop();
			if (first == final_state)
			{
				stack<vector<int>>result;
				while (first != m_init_state)
				{
					result.push(first);
					first = father[first];
				}
				while (result.size())
				{
					results.push_back(result.top());
					result.pop();
				}
				end = ::GetTickCount();//成功的
				//printf("消耗时间  %d",begin);
				return true;
			}
			int start_point = find(first.begin(), first.end(), 0) - first.begin();//寻找0的位置
			int x = start_point / 3;//平面坐标
			int y = start_point % 3;
			for (int i = 0; i < 4; i++) 
			{
				int temp_x = x + dx[i];
				int temp_y = y + dy[i];//可交换元素坐标
				vector<int>father_ = first;
				if (temp_x >= 0 && temp_x < 3 && temp_y >= 0 && temp_y < 3) {
					swap(first[temp_x * 3 + temp_y], first[start_point]);
					if (!hash.count(first)) {//使用一个哈希表来防止重复状态
						stringstream ss;
						copy(first.begin(), first.end(), ostream_iterator<int>(ss, ""));
						hash[first] = ss.str();
						father[first] = father_;
						bfs_q.push(first);
					}
					swap(first[temp_x * 3 + temp_y], first[start_point]);
				}//防止越界
			}
		}
		end = ::GetTickCount();//失败的
		return false;
	}

	// dfs to find the solution
	bool DFS(vector<vector<int>>& results)
	{
		begin = ::GetTickCount();//返回自设备启动后的毫秒数
		stack<vector<int>> dfs_s;//使用栈来保存状态
		map<vector<int>, string> hash;
		map<vector<int>, vector<int>> father;//每一步状态
		map<vector<int>, int>depth;//记录深度
		int dx[] = { -1,1,0,0 };
		int dy[] = { 0,0,-1,1 };
		dfs_s.push(m_init_state);
		depth[m_init_state] = 0;
		while (!dfs_s.empty())
		{
			vector<int>temp = dfs_s.top();
			dfs_s.pop();
			if (temp == final_state) 
			{
				stack<vector<int>>s;
				while (temp != m_init_state) 
				{
					s.push(temp);
					temp = father[temp];
				}
				while (s.size()) {
					results.push_back(s.top());
					s.pop();
				}
				end = ::GetTickCount();//成功的
				return true;
			}
			int zero = find(temp.begin(), temp.end(), 0) - temp.begin();//寻找0的位置
			int x = zero / 3;
			int y = zero % 3;
			int temp_depth = depth[temp];
			for (int i = 0; i < 4; i++) 
			{
				int temp_x = x + dx[i];
				int temp_y = y + dy[i];//计算交换元素的位置
				vector<int>father_ = temp;
				if (temp_x >= 0 && temp_x < 3 && temp_y >= 0 && temp_y < 3) 
				{
					swap(temp[temp_x * 3 + temp_y], temp[zero]);
					if (!hash.count(temp)) 
					{//使用一个哈希表来防止重复状态
						stringstream ss_temp;
						copy(temp.begin(), temp.end(), ostream_iterator<int>(ss_temp, ""));
						hash[temp] = ss_temp.str();
						father[temp] = father_;
						depth[temp] = temp_depth + 1;
						if (depth[temp] <= Max_Len) 
						{
							dfs_s.push(temp);
						}
					}
					swap(temp[temp_x * 3 + temp_y], temp[zero]);
				}//防止越界
			}
		}
		end = ::GetTickCount();//成功的
		return false;
	}

	// ucs to find the solution
	bool UCS(vector<vector<int>>& results)
	{
		begin = ::GetTickCount();//返回自设备启动后的毫秒数
		priority_queue<status, vector<status>, cmp>U_open;//优先队列存储
		map<vector<int>, string> hash;//hash判断是否存在重复的情况
		map<vector<int>, vector<int>> father; //记录父节点
		int dx[] = { -1,1,0,0 };
		int dy[] = { 0,0,-1,1 };
		status node;
		node.v = m_init_state;
		node.depth = 0;
		U_open.push(node);
		while (!U_open.empty()) 
		{//当队列非空的时候
			vector<int> temp = U_open.top().v;
			int temp_depth = U_open.top().depth;
			U_open.pop();//取队首元素
			if (temp == final_state) 
			{
				stack<vector<int>>s;
				while (temp != m_init_state) 
				{
					s.push(temp);
					temp = father[temp];
				}
				while (s.size()) 
				{
					results.push_back(s.top());
					s.pop();
				}
				end = ::GetTickCount();//成功的
				return true;
			}//判断是否到结束的状态
			int zero = find(temp.begin(), temp.end(), 0) - temp.begin();//寻找到空格的位置
			int x = zero / 3;
			int y = zero % 3;
			for (int i = 0; i < 4; i++) 
			{
				int temp_x = x + dx[i];
				int temp_y = y + dy[i];//计算交换元素的位置
				vector<int>father_ = temp;
				if (temp_x >= 0 && temp_x < 3 && temp_y >= 0 && temp_y < 3) 
				{
					swap(temp[temp_x * 3 + temp_y], temp[zero]);
					if (!hash.count(temp)) 
					{//使用一个哈希表来防止重复状态
						stringstream ss_temp;
						copy(temp.begin(), temp.end(), ostream_iterator<int>(ss_temp, ""));
						hash[temp] = ss_temp.str();
						father[temp] = father_;
						status temp_node;
						temp_node.v = temp;
						temp_node.depth = temp_depth + 1;
						U_open.push(temp_node);
					}
					swap(temp[temp_x * 3 + temp_y], temp[zero]);
				}//防止越界
			}
		}
		end = ::GetTickCount();//成功的
		return false;
	}

private:
	vector<int> m_init_state;
	vector<int> final_state = { 1, 2, 3, 4, 5, 6, 7, 8, 0 };
};

// test function for 8-puzzle problem
void test(const vector<int>& init_state) {
	AI_Puzzle puzzle;
	puzzle.setInitState(init_state);
	vector<vector<int>> results;
	if (puzzle.solution(results)) {
		printf("solution for the initial state: ");
		for (int i = 0; i < init_state.size(); i++) 
			printf("%d ", init_state[i]);
		printf("\n");
		for (int i = 0; i < results.size(); i++) {
			printf("step: %03d:", i);
			for (int j = 0; j < results[i].size(); j++) {
				printf(" %d", results[i][j]);
			}
			printf("\n");
		}
	}
	else {
		printf("no solution for the initial state: ");
		for (int i = 0; i < init_state.size(); i++) 
			printf("%d ", init_state[i]);
		printf("\n");
	}
	printf("\n");
}

int main(int argc, char** argv)
{
	// This is the code for testing the 8-puzzle problem in
	//
	//  'The first project homework for Artifical Intelligence'
	// 
	// Please fill in the code of class 'AI_Puzzle'
	// and write your design, running tests, analysis and etc. into your report
	// Be careful: in each step, we can ONLY exchange with ONE neighbor of digit 0, horizontally or vertically
	//
	// Good Luck!
	//
	// Yangang Wang, 2021/8/15, @SEU

	// Test 1
	//	5   1   2
	//	6   3   0
	//	4   7   8
	vector<int> init_state1 = { 5, 1, 2, 6, 3, 0, 4, 7, 8 };
	test(init_state1);

	// Test 2
	//
	//	2   8   3
	//	1   6   4
	//	7   5   0
	vector<int> init_state_2 = { 2, 8, 3, 1, 6, 4, 7, 5, 0 };
	test(init_state_2);

	// Test 3
	//
	//	1   0   2
	//	3   4   5
	//	6   7   8
	vector<int> init_state_3 = { 1, 0, 2, 3, 4, 5, 6, 7, 8 };
	test(init_state_3);

	// Test 4
	//
	//	4   3   5
	//	6   0   8
	//	2   1   7
	vector<int> init_state_4 = { 4, 3, 5, 6, 0, 8, 2, 1, 7 };
	test(init_state_4);

	// Test 5
	//
	//	1   7   3
	//	0   5   4
	//	6   2   8
	vector<int> init_state_5 = { 1, 7, 3, 0, 5, 4, 6, 2, 8 };
	test(init_state_5);

	return 0;
}